54C - First Digit Law - CodeForces Solution

#include <bits/stdc++.h>
#pragma GCC optimize (2)
#define MOD 998244353
#define NUM 200005
#define fi first
#define se second
#define pb push_back
#define me memset
//#define rep(a,b,c) for(int a=b;a<=c;++a)
//#define per(a,b,c) for(int a=b;a>=c;--a)
#define rep(a,b,c) for(int a=b;a<c;++a)
#define per(a,b,c) for(int a=b;a>c;--a)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll x,ll y) {
	return y==0?x:gcd(y,x%y);
}
ll lcm(ll x,ll y) {
	return x/gcd(x,y)*y;
}
ll lowbit(ll x) {
	return x&-x;
}
//template <class T> lowbit(T x) {
//	return x&(-x);
//}
//int read() {
//	int ans=0;
//	char c=getchar();
//	while(!isdigit(c)) {
//		c=getchar();
//	}
//	while(isdigit(c)) {
//		ans=ans*10+c-'0';
//		c=getchar();
//	}
//
//	return ans;
//}
inline int read() { //?????????????????????
	register int x=0,f=1;
	register char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*f;
}
char cread() {
	char c=getchar();
	while(c==' '||c=='\n') {
		c=getchar();
	}
	return c;
}

//	priority_queue<int,vector<int>,greater<int> > a;

bool cmp(int x,int y) {
//	return x>y;
	bool f1=x&1;
	bool f2=y&1;
	if(f1&&f2){
		return x<y;
	}else if(f1){
		return 1;
	}else if(f2){
		return 0;
	}else{
		return x>y;
	}
}
const int INF=0x3f3f3f3f;
double dp[1005];
double p[1005];
//ǰiλ����j����ͷΪ1 
ll n,k,l,r; 
double ans;
ll cnt(ll n){
	ll cur=0;
	ll x=1;
	ll now=0;
	ll high=0;
	ll nn=n;
	while(nn){
		high=nn%10;
		nn/=10;
		++now;
	}
	--now;
	for(int i=1;i<=now;++i,x*=10){
		cur+=x;
	}
	if(high>1)cur+=x;
	else if(high==1){
		cur+=n-x+1;
	} 
	return cur;
	
}
void solve() {
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>l>>r;
		ll a=cnt(r)-cnt(l-1);
		p[i]=1.0*a/(r-l+1);
	}
	cin>>k;
	dp[0]=1;
	for(int i=1;i<=n;++i){
		for(int j=n;j>=0;--j){
			dp[j]=dp[j]*(1-p[i]);
			if(j>0){
				dp[j]+=dp[j-1]*p[i];
			}
		}
	}
	for(int i=0;i<=n;++i){
		if(i*100>=n*k){
			ans+=dp[i];
		}
	}
	printf("%.15f",ans);
	
	
	return;
}

int main() {
//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t=1;
//	cin>>t;
//	build();
	while(t--) {
		
		solve();

		if(t) {
			cout<<"\n";
		}

	}

	return 0;
}